package org.leetcode.middle.leetcode102;

import org.leetcode.TreeNode;
import org.w3c.dom.ls.LSInput;

import java.util.*;

public class Solution
{


    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> resList = new ArrayList<>();

        checkFun02(root,resList);

        return resList;
    }

    public void checkFun00(TreeNode node, List<List<Integer>> resList) {
        if (node==null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);

        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list =new ArrayList<>();
            while (size>0){
                TreeNode tempNode = queue.poll();
                list.add(tempNode.val);

                if (tempNode.left!=null){
                    queue.add(tempNode.left);
                }
                if (tempNode.right!=null){
                    queue.add(tempNode.right);
                }
                size--;
            }
            resList.add(list);
        }

    }


    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node, List<List<Integer>> resList) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<>();
            int len = que.size();

            //添加下一层的所有节点到队列中，根据队列的长度来进行遍历
            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }
    }


    public void checkFun03(TreeNode node,List<List<Integer>> resList)
    {
        if (node==null)
        {
            return;
        }

        Queue<TreeNode> que=new LinkedList<>();

        que.offer(node);

        while (!que.isEmpty())
        {
            ArrayList<Integer> itemList = new ArrayList<>();

            int length = que.size();

            while (length>0)
            {

                TreeNode treeNode = que.poll();
                itemList.add(treeNode.val);

                if (treeNode.left!=null)
                {
                    que.offer(treeNode.left);
                }

                if (treeNode.right!=null)
                {
                    que.offer(treeNode.right);
                }

                length--;
            }

            resList.add(itemList);
        }


    }


    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode node9 = new TreeNode(9);
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7);
        TreeNode node6 = new TreeNode(6);
        TreeNode node5 = new TreeNode(5, node8, node9);
        TreeNode node4 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3, node6, node7);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3); // 根节点


        solution.levelOrder(node1);


    }
}
